#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <iostream>
#include <istream>
#include <map>
#include <vector>
using ll = int64_t;
#define sl static inline
#define printf
const ll inf=1e9+7;
std::vector<ll> a,b,dp,dpf;
std::map<ll, ll> rstep;
ll n,m;
struct Mu{
    ll num,idx;
    inline bool operator<(const Mu&o)const{
        return num<o.num;
    }
};
std::vector<Mu> cminuse;

sl ll minuse(ll val){
    if(cminuse[val].idx!=inf){
        return cminuse[val].idx;
    }
    for(ll i=1;i<=m;i++){
        const ll num = (val+a[i]-1)/a[i];
        cminuse[val]=std::min(cminuse[val],{num*b[i],i});
    }
    return cminuse[val].idx;
}

sl void solve(){
    ll ans=0;
    std::cin>>n>>m;
    a.clear(),b.clear(),dp.clear(),dpf.clear(),rstep.clear(),cminuse.clear();
    a.resize(m+1),b.resize(m+1),dp.resize(n+1,inf),dpf.resize(n+1,inf),cminuse.resize(n+1,{inf,inf});
    dp[0]=0;
    for(ll i=1;i<=m;i++){
        std::cin>>a[i];
    }
    for(ll i=1;i<=m;i++){
        std::cin>>b[i];
    }
    for(ll i=1;i<=m;i++){
        for(ll j=a[i];j<=n;j++){
            const ll ndp=dp[j-a[i]]+b[i];
            // printf("i=%lld, j=%lld, ndp=%lld\n",i,j,ndp);
            if(ndp<dp[j]){
                // printf("got new min %lld\n",ndp);
                dp[j]=ndp;
                dpf[j]=j-a[i];
            }
        }
    }
    for(ll i=1;i<=m;i++){
        for(ll j=n-a[i];j>=1;j--){
            dp[j]=std::min(dp[j],dp[j+a[i]]+b[i]);
        }
    }
    printf("dp[]: ");
    for(ll i=1;i<=n;i++){
        printf("%lld ",dp[i]);
    }
    printf("\n");
    printf("dpf[]: ");
    for(ll i=1;i<=n;i++){
        printf("%lld ",dpf[i]);
    }
    printf("\n");
    printf("minuse(%lld)=%lld\n",n,minuse(n));
    ll nuse=0;
    for(ll i=1;i<=n;){
        const ll use=minuse(n-i),k=i+a[use];
        nuse+=b[use];
        for(ll j=i+1;j<=k&&j<=n;j++){
            if(dp[k-j]==inf){
                std::cout<<"-1\n";
                return;
            }else{
                ans=std::max(ans,dp[k-j]+nuse);
            }
        }
        i=k;
    }
    std::cout<<ans<<"\n";
}

int main(){
    #ifdef printf
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);
    #endif
    ll c,t;
    std::cin>>c>>t;
    while(t--){
        solve();
    }
}